#ifndef BST_H_INCLUDED
#define BST_H_INCLUDED
#include <unistd.h>
#include <iostream>
using namespace std;
class BSTree{
    struct Node{
        int value;
        Node *right;
        Node * left;

        Node(int x = 0, Node * l = NULL,Node * r = NULL):left(l), right(r),value(x){
        }


    };


public:
    void insert_Node(int x)
    {
        insert_node(x,root);

    }

    void remove_node(int x)
    {
        cout << "remove " << x << endl;
        remove_node(x, root);

    }

    BSTree(){
        root = NULL;
        thesize = 0;
    }


    ~BSTree()
    {
        makeEmpty(root);
    }

    void displayAll()
    {
        displayall(root);

    }

    BSTree & operator=(const BSTree & rhs)
    {
        makeEmpty(root);
        root = clone(rhs.root);
    }

    BSTree(const BSTree & rhs)
    {
        *this = rhs;
    }



private:
    Node * root;
    int thesize;


    Node * clone(Node * t)
    {
        if(t == NULL)
            return NULL;
        cout << "clone " << t->value << endl;
        return new Node(t->value, clone(t->left), clone(t->right) );
    }

    void displayall(Node * t)
    {
        if(t == NULL)
            return;
        displayall(t->left);
        cout << t->value << endl;
        displayall(t->right);

    }

    void insert_node(int x, Node *&t)
    {
        if(t == NULL){
            t = new Node(x);
            thesize++;
        }
        else if(x > t->value )
            insert_node(x,t->right);
        else if(x < t->value)
            insert_node(x,t->left);
        else{

        }

    }

    void remove_node(int x , Node *&t)
    {


        if(t == NULL)
            return;
        if(x > t->value)
            remove_node(x,t->right);
        else if(x < t->value)
            remove_node(x, t->left);
        else if(x == t->value && t->left != NULL && t->right != NULL)
        {
            /*find minimal node n of right sub-tree and replace this node then remove n*/
            Node * miniRight = findmin(t->right);
            t->value = miniRight->value;
            remove_node(t->value, t->right);
        }
        else /*note*/
        {
            Node * oldNode = t;
            if(oldNode->left != NULL)
                t = oldNode->left;
            else
                t = oldNode->right;
            thesize--;
            delete oldNode;
        }
    }

    Node * findmin(Node * t)
    {
        if(t == NULL)
            return NULL;
        if(t->left != NULL)
            findmin(t->left);
        else
            return t;
    }

    Node * findmax(Node * t)
    {
        if(t == NULL)
            return NULL;
        if(t->right != NULL)
            findmax(t->right);
        else
            return t;

    }

    void makeEmpty(Node *& t)
    {
        if(t == NULL)
            return;

        makeEmpty(t->left);
        makeEmpty(t->right);

        if(t->left == NULL && t->right == NULL)
        {
            cout << "make " << t->value << " empty " << endl;
               delete t;
               t = NULL;

        }
    }

};



#endif // BST_H_INCLUDED
